package MysingleList; /**
 * @Author：JIAMIN_TANG
 * @Description:用于测试单链表常用方法的实现的功能测试
 * @CreateTime：2025/10/12 17:44
 */
import listiterface.IList;
import myexception.ListIndexOutOfBoundsException;

import java.util.Scanner;
public class Test {
    //测试链表的size、contains、display功能
    private static void test1(){
        MySingleList mysinglelist = new MySingleList();
        mysinglelist.createList();

        //测试size()方法
        if(mysinglelist.size()==5){
            System.out.println("获取链表长度size方法测试通过！");
        }else{
            System.out.println("测试不通过！");
        }

        //测试contains()方法
        if(mysinglelist.contains(23)){
            System.out.println("查找元素是否存在contains方法测试通过！");
        }else{
            System.out.println("测试不通过！");
        }

        mysinglelist.display();
    }

    //测试头插法addFirst的功能
    private static void test2(){
        MySingleList mysinglelist1 = new MySingleList();
        //在非空链表中头插元素
        System.out.println("非空链表头插元素：");
        mysinglelist1.createList();
        System.out.print("原链表：");
        mysinglelist1.display();
        System.out.print("使用addFirst之后的新链表：");
        mysinglelist1.addFirst(100);
        mysinglelist1.display();

        System.out.println();

        //在空链表中头插若干元素
        System.out.println("空链表头插元素：");
        MySingleList mysinglelist2 = new MySingleList();
        mysinglelist2.addFirst(1);
        mysinglelist2.addFirst(2);
        mysinglelist2.addFirst(3);
        mysinglelist2.addFirst(4);
        mysinglelist2.addFirst(5);
        mysinglelist2.display();//注意这里输出的是5 4 3 2 1   因为是头插，所以最新插入的元素在链表的最前面，最先插入的元素在链表的最后
    }

    //测试尾插法addLast
    private static void test3(){
        MySingleList mysinglelist = new MySingleList();
        //在非空链表中头插元素
        mysinglelist.createList();
        System.out.print("原链表：");
        mysinglelist.display();

        System.out.print("使用addLast之后的新链表：");
        mysinglelist.addLast(1);
        mysinglelist.display();
    }

    //测试任意位置插入addIndex
    private static void test4(){
        MySingleList mysinglelist1 = new MySingleList();
        mysinglelist1.createList();
        System.out.print("原链表：");
        mysinglelist1.display();

        //在链表头部插入
        System.out.print("在链表的第0个位置插入1之后的新链表：");
        try {
            mysinglelist1.addIndex(0, 1);
        }catch(ListIndexOutOfBoundsException e){
            e.printStackTrace();
        }
        System.out.print("插入后链表：");
        mysinglelist1.display();

        //在链表中间插入
        System.out.print("在链表的第3个位置插入2之后的新链表：");
        try {
            mysinglelist1.addIndex(3, 2);
        }catch(ListIndexOutOfBoundsException e){
            e.printStackTrace();
        }
        System.out.print("插入后链表：");
        mysinglelist1.display();

        //在链表尾部插入
        System.out.print("在链表的第"+mysinglelist1.size()+"个位置插入3之后的新链表：");
        try{
        mysinglelist1.addIndex(mysinglelist1.size(),3);
        }catch(ListIndexOutOfBoundsException e){
            e.printStackTrace();
        }
        System.out.print("插入后链表：");
        mysinglelist1.display();

        //在链表位置不合法处插入
        System.out.print("在链表的第100个位置插入4之后的新链表：");
        System.out.print("插入后链表：");
        try{
        mysinglelist1.addIndex(100,4);
        }catch(ListIndexOutOfBoundsException e){
            e.printStackTrace();
        }
        mysinglelist1.display();

        System.out.print("在链表的第-1个位置插入5之后的新链表：");
        try{
        mysinglelist1.addIndex(-1,5);
        }catch(ListIndexOutOfBoundsException e){
            e.printStackTrace();
        }
        System.out.print("插入后链表：");
        mysinglelist1.display();

    }

    //删除链表中某一元素值的节点remove方法的测试
    private static void test5(){
        IList mysinglelist = new MySingleList();
        mysinglelist.addLast(23);
        mysinglelist.addLast(34);
        mysinglelist.addLast(23);
        mysinglelist.addLast(54);
        mysinglelist.addLast(23);
        System.out.print("原链表：");
        mysinglelist.display();

        mysinglelist.remove(45);
        mysinglelist.display();

        mysinglelist.remove(23);
        mysinglelist.display();
    }

    //删除某个值在链表中的所有位置的节点removeAllKey方法的测试
    private static void test6() {
        IList mysinglelist = new MySingleList();
        mysinglelist.addLast(23);
        mysinglelist.addLast(23);
        mysinglelist.addLast(23);
        mysinglelist.addLast(23);
        mysinglelist.addLast(23);
        mysinglelist.display();

        mysinglelist.removeAllKey(23);
        mysinglelist.display();
    }

    //clear()方法的测试
    private static void test7() {
        IList mysinglelist = new MySingleList();
        mysinglelist.addLast(23);
        mysinglelist.addLast(23);
        mysinglelist.addLast(23);
        mysinglelist.addLast(23);
        mysinglelist.addLast(23);
        mysinglelist.display();

        System.out.print("清空链表之后：");
        mysinglelist.clear();
        mysinglelist.display();
    }

    //测试reverseList方法
    private static void test8() {
        MySingleList mysinglelist = new MySingleList();
        mysinglelist.addLast(1);
        mysinglelist.addLast(2);
        mysinglelist.addLast(3);
        mysinglelist.addLast(4);
        mysinglelist.addLast(5);
        mysinglelist.display();

        System.out.print("反转链表之后：");
        mysinglelist.reverseList();
        mysinglelist.display();
    }

    //测试middleNode方法
    private static void test9(){
        MySingleList mysinglelist = new MySingleList();
        mysinglelist.addLast(1);
        mysinglelist.addLast(2);
        mysinglelist.addLast(3);
        mysinglelist.addLast(4);
        mysinglelist.addLast(5);
        mysinglelist.display();

        System.out.print("链表的中间节点是：");
        System.out.println(mysinglelist.middleNode(mysinglelist.head).val);
//        mysinglelist.display(mysinglelist.middleNode(mysinglelist.head));
    }

    private static void test10(){
        MySingleList mysinglelist = new MySingleList();
        mysinglelist.addLast(10);
        mysinglelist.addLast(9);
        mysinglelist.addLast(8);
        mysinglelist.addLast(7);
        mysinglelist.addLast(6);
        mysinglelist.addLast(5);
        mysinglelist.addLast(4);
        mysinglelist.addLast(3);
        mysinglelist.addLast(2);
        mysinglelist.addLast(1);



        mysinglelist.display();

        System.out.print("请输入要查找的倒数第k个节点的k值(1~10)：");
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        if(mysinglelist.kthToLast(k)==-1){
            System.out.println("请输入在1到10范围内的数");
        }
        else {
            System.out.print("找到链表的倒数第"+k+"个节点的值为："+mysinglelist.kthToLast(k));
        }
    }
    public static void main1(String[] args) {
//        test1();//测试链表的size、contains、display功能
//        test2();//测试头插法addFirst的功能
//        test3();//测试尾插法addLast
//        test4();//测试任意位置插入addIndex
//        test5();//删除链表中某一元素值的节点remove方法的测试
//        test6();//删除某个值在链表中的所有位置的节点removeAllKey方法的测试
//        test7();//clear()方法的测试
//        test8();//测试reverseList方法
//        test9();//测试middleNode方法
//        test10();//测试kthToLast方法

    }

    //合并两个链表
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode headA,
                                               MySingleList.ListNode headB){
        //定义一个傀儡节点（虚拟节点）：头节点        此时涉及到了获取静态内部类对象
        MySingleList.ListNode newH = new MySingleList.ListNode(-1);

        MySingleList.ListNode tmp = newH;

        while(headA != null && headB !=null){
            if(headA.val < headB.val){
                tmp.next = headA;
                headA = headA.next;
            }else{
                tmp.next = headB;
                headB = headB.next;
            }
            tmp = tmp.next;
        }
        if(headA != null){
            tmp.next = headA;
        }
        if(headB != null){
            tmp.next = headB;
        }
        return newH.next;
    }

    public static void main2(String[] args){//合并两个链表，节点按大小重新排序
        MySingleList mysinglelist1 = new MySingleList();
        mysinglelist1.addLast(12);
        mysinglelist1.addLast(23);
        mysinglelist1.addLast(34);
        mysinglelist1.addLast(45);
        mysinglelist1.addLast(56);
        mysinglelist1.addLast(67);
        mysinglelist1.display();

        MySingleList mysinglelist2 = new MySingleList();
        mysinglelist2.addLast(13);
        mysinglelist2.addLast(25);
        mysinglelist2.addLast(35);
        mysinglelist2.addLast(146);
        mysinglelist2.addLast(156);
        mysinglelist2.display();

        System.out.println(" ==================== ");
        System.out.println(" ========合并========= ");

        MySingleList.ListNode ret = mergeTwoLists(mysinglelist1.head,mysinglelist2.head);

        mysinglelist2.display(ret);
    }

    public static void main3(String[] args){
        MySingleList mysinglelist1 = new MySingleList();
        mysinglelist1.addLast(12);
        mysinglelist1.addLast(26);
        mysinglelist1.addLast(14);
        mysinglelist1.addLast(45);
        mysinglelist1.addLast(16);
        mysinglelist1.addLast(67);
//        mysinglelist1.display();

        MySingleList.ListNode ret = mysinglelist1.partition(25);
        mysinglelist1.display(ret);
    }

    public static void main4(String[] args){
        MySingleList mysinglelist1 = new MySingleList();
        mysinglelist1.addLast(1);
        mysinglelist1.addLast(2);
        mysinglelist1.addLast(3);
        mysinglelist1.addLast(3);
        mysinglelist1.addLast(2);
        mysinglelist1.addLast(1);

        MySingleList mysinglelist2 = new MySingleList();
        mysinglelist2.addLast(1);
        mysinglelist2.addLast(2);
        mysinglelist2.addLast(3);
        mysinglelist2.addLast(4);
        mysinglelist2.addLast(5);
        mysinglelist2.addLast(6);

        MySingleList mysinglelist3 = new MySingleList();
        mysinglelist3.addLast(4);
        mysinglelist3.addLast(5);
        mysinglelist3.addLast(6);
        mysinglelist3.addLast(5);
        mysinglelist3.addLast(4);

        MySingleList mysinglelist4 = new MySingleList();
        mysinglelist4.addLast(4);
        mysinglelist4.addLast(5);
        mysinglelist4.addLast(6);
        mysinglelist4.addLast(7);
        mysinglelist4.addLast(8);



        System.out.println(mysinglelist1.chkPalindrome());
        System.out.println(mysinglelist2.chkPalindrome());
        System.out.println(mysinglelist3.chkPalindrome());
        System.out.println(mysinglelist4.chkPalindrome());
    }

    //输出两个链表，找出他们的第一个公共节点
    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA,MySingleList.ListNode headB){
        //1.假定A链表长，B链表短
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;

        //2.分别求两个链表的长度
        int len1 = 0;
        int len2 = 0;
        while(pl!=null){
            len1++;
            pl = pl.next;
        }

        while(ps!=null){
            len2++;
            ps = ps.next;
        }
        //这里修改完len1和len2的值之后pl和ps都指向null了，所以在这里要让他们重新指向headA和headB
        pl = headA;
        ps = headB;

        //3.求长度的差值len
        //len<0 pl=headB ps=heasA,len=len1-len2
        int len = len1-len2;
        if(len<0){
            pl = headB;
            ps = headA;
            len = len2-len1;
        }

        //4.确定pl指向的节点，一定是长链表，ps指向的节点一定是短炼表

        //5.让pl先走len步
        while(len != 0){
            pl = pl.next;
            len--;
        }
        //6.ps和pl同时走直到相遇
        while(pl != ps){
            pl = pl.next;
            ps = ps.next;
        }

        //如果没有相遇，那么pl = null
        if(pl == null){
            return null;
        }
        return pl;
    }
    public static void main5(String[] args){
       //构造公共部分节点(8-->4-->5)
        MySingleList.ListNode common1 = new MySingleList.ListNode(8);
        MySingleList.ListNode common2 = new MySingleList.ListNode(4);
        MySingleList.ListNode common3 = new MySingleList.ListNode(5);
        common1.next = common2;
        common2.next = common3;

        //链表A的构造
        MySingleList listA = new MySingleList();
        listA.head = new MySingleList.ListNode(4);
        listA.head.next = new MySingleList.ListNode(1);
        listA.head.next.next = common1; //连接公共部分

        //链表B的构造
        MySingleList listB = new MySingleList();
        listB.head = new MySingleList.ListNode(5);
        listB.head.next = new MySingleList.ListNode(6);
        listB.head.next.next = common1; //连接公共部分

        //此时第一个公共节点值为8
        MySingleList.ListNode intersection = getIntersectionNode(listA.head,listB.head);
        System.out.println(intersection.val);
    }

    public static void main6(String[] args){
        MySingleList mysinglelist1 = new MySingleList();
        mysinglelist1.addLast(12);
        mysinglelist1.addLast(23);
        mysinglelist1.addLast(34);
        mysinglelist1.addLast(45);
        mysinglelist1.addLast(56);
        mysinglelist1.addLast(67);
        mysinglelist1.display();
        System.out.println("=================");

        mysinglelist1.createLoop();
        boolean hasCycle = mysinglelist1.hasCycle();
        System.out.println(hasCycle);
    }

    public static void main(String[] args){
        // 测试1：无环链表
        testNoCycleCase();

        // 测试2：有环链表（环入口在中间节点）
        testCycleWithMiddleEntry();

        // 测试3：环入口为头节点
        testCycleWithHeadEntry();

        // 测试4：单节点成环
        testSingleNodeCycle();
    }

    //测试无环链表
    private static void testNoCycleCase(){
        System.out.println("==测试无环链表==");
        MySingleList list = new MySingleList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);

        MySingleList.ListNode entry = list.detectCycle(list.head);
        if(entry == null){
            System.out.println("测试通过无环是返回null");
        }else{
            System.out.println("测试失败:无环时返回错误节点"+entry.val);
        }
    }

    //测试环入口在中间节点的情况
    private static void testCycleWithMiddleEntry(){
        System.out.println("==测试环入口在中间节点==");
        MySingleList list = new MySingleList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);//环入口
        list.addLast(4);
        list.addLast(4);

        //手动创建环5———>3
        MySingleList.ListNode cur = list.head;
        MySingleList.ListNode entryNode = null;
        while(cur.next != null){
            if(cur.val == 3){
                entryNode = cur;//记录环入口点
            }
            cur = cur.next;
        }
        cur.next = entryNode;//形成环

        MySingleList.ListNode result = list.detectCycle(list.head);
        if(result != null && result.val == 3){
            System.out.println("测试通过:正确找到环入口点"+result.val);
        }else{
            System.out.println("测试失败:未正确找到环入口");
        }
        System.out.println();
    }

    //测试环入口为头节点的情况
    private static void testCycleWithHeadEntry(){
        System.out.println("==测试环入口为头节点==");
        MySingleList list = new MySingleList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);

        //手动创建环3———>1
        MySingleList.ListNode cur = list.head;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = list.head;//形成环

        MySingleList.ListNode result = list.detectCycle(list.head);
        if(result != null && result.val == 1){
            System.out.println("测试通过:正确找到环入口点"+result.val);
        }else{
            System.out.println("测试失败:未正确找到环入口");
        }
        System.out.println();
    }

    //测试单节点成环的情况
    private static void testSingleNodeCycle(){
        System.out.println("==测试单节点成环==");
        MySingleList list = new MySingleList();
        list.addLast(1);//唯一节点，自己成环

        //手动创建换:1———>1
        list.head.next = list.head;

        MySingleList.ListNode result = list.detectCycle(list.head);
        if(result != null && result.val == 1){
            System.out.println("测试通过:正确找到环入口点"+result.val);
        }else{
            System.out.println("测试失败:未正确找到环入口");
        }
    }
}
